1156E - Special Segments of Permutation - CodeForces Solution

// reminder: i have autism

#include <iostream>
#include<math.h>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <deque>
#include <random>
#include <algorithm>
#include <iterator>
#include <numeric>
#include <tuple>
#include <thread>
#include <chrono>
#include <iomanip>    
typedef long long ll;
using namespace std;
 


const ll mod = 1e9+7;
const ll inf = 1e18+1e17;
 
int bitcount(ll n) { return n == 0 ? 0 : bitcount(n & (n - 1)) + 1;}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}
ll binexp(ll a, ll b){
    if (!b) return 1;
    ll res = binexp(a, b/2);
    res = (res*res)%mod;
    if(b%2) res = (res*a)%mod;
    return res;
}
ll rev(ll x) {return binexp(x, mod - 2);}



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    int n;
    cin >> n;
    vector<int> p(n+1,0), inv(n+1,0);
    vector<int> left_mx(n+1, -1), right_mx(n+1, n+1);
    for(int i = 1;i<=n;i++){
        cin >> p[i];
        inv[p[i]] = i;
    }
    stack<int> st;
    for(int i = 1;i<=n;i++){
        while(!st.empty() && st.top()<p[i]) st.pop();
        if(!st.empty()) left_mx[i] = st.top();
        st.push(p[i]);
    }
    while(!st.empty()) st.pop();
    for(int i = n;i>=1;i--){
        while(!st.empty() && st.top()<p[i]) st.pop();
        if(!st.empty()) right_mx[i] = st.top();
        st.push(p[i]);
    }
    ll ans = 0;
    for(int i = 1;i<=n;i++){
        int left = left_mx[i], right = right_mx[i];
        int l,r;
        if(left==-1) l = 0;
        else l = inv[left];
        if(right==n+1) r = n+1;
        else r = inv[right];
        if(i - l >= r - i){
            //go to the right part
            for(int j = i+1; j<r;j++){
                if(j>n) break;
                int want = p[i] - p[j];
                int index = inv[want];
                if(index < i && index > l) ans++;
            }
        }
        else{
            //left part
            for(int j = l + 1; j<i;j++){
                int want = p[i] - p[j];
                int index = inv[want];
                if(index > i && index < r) ans++;
            }
        }
    }
    cout << ans << endl;
}